// copyright:no copyright,use it if you like
// license boilerplate:BSD 3-Clause
// filename:QuickSort.h
// author:Tempest(https://gitee.com/Tempest56890)
// date:2021-12-13
// brief:implement the quicksort

#ifndef __TEMPEST_QUICKSORT__
#define __TEMPEST_QUICKSORT__

#include <iostream>
#include <vector>
#include <cstdlib>

template <typename Comparable>
// i/o param:A(a Vector)/left/right
// implement of the function of small
// scale of data set.
void insertionsort(std::vector<Comparable> & A,int left,int right) {
    long int i,j;
    // tmp to temporarily store data.
    Comparable tmp;
    for (i=left+1;i<=right;++i) {
        tmp=A[i];
        for (j=i;j>left && tmp<A[j-1];--j)
            A[j]=A[j-1];
        A[j]=tmp;
    }
};

template <typename Comparable>
// i/o param:A(a Vector)/left/right
// function call insertionsort() for small
// scale of data set.
// example:
//    (Temporarily omitted.)
void quicksort(std::vector<Comparable> & A,int left,int right) {
    int L=left,R=right;
    int r1=-1,r2=-1,r3=-1;
    if (R-L<11) {
        insertionsort(A,L,R);
    }
    else {
        int i=L+1,j=R-2;
        Comparable tmp,_tmp;
        // r1,r2,r3 randomly store three subscripts.
        while (r1<L || r1>R) r1=(rand()%(R-L+1))+L;
        while (r2<L || r2>R || r2==r1) r2=(rand()%(R-L+1))+L;
        while (r3<L || r3>R || r3==r1 || r3==r2) r3=(rand()%(R-L+1))+L;
        // compare and exchange to save some time.
        if (A[r1]>A[r2]) {tmp=A[r1];A[r1]=A[r2];A[r2]=tmp;}
        if (A[r1]>A[r3]) {tmp=A[r1];A[r1]=A[r3];A[r3]=tmp;}
        if (A[r2]>A[r3]) {tmp=A[r2];A[r2]=A[r3];A[r3]=tmp;}
        tmp=A[L];A[L]=A[r1];A[r1]=tmp;
        tmp=A[R-1];A[R-1]=A[r3];A[r3]=tmp;
        tmp=A[R];A[R]=A[r2];A[r2]=tmp;
        // tmp stores the pivot data!!!
        tmp=A[R];
        while (i<j) {
            // ignore the data equalling to tmp.
            while (i<=R-2 && A[i]<=tmp) ++i;
            while (j>=L+1 && A[j]>=tmp) --j;
            if (i<j) {
                _tmp=A[i];A[i]=A[j];A[j]=_tmp;
                ++i;
                --j;
            }
        }
        // give back the pivot data.
        tmp=A[R];A[R]=A[i];A[i]=tmp;
        // recursion of left and right subsets.
        quicksort(A,L,i-1);
        quicksort(A,i+1,R);
    }
};

template <typename Comparable>
// i/o param:A(a Vector)
// function call quicksort() twice to
// make sure the data set correctly sorted.
// example:
//    (Temporarily omitted.)
void sort(std::vector<Comparable> & A) {
    quicksort(A,0,(int)A.size()-1);
    quicksort(A,0,(int)A.size()-1);
};

#else
#endif
